package com.company.Sort2;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}14:15
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {3,2,1};
        System.out.println(Arrays.toString(quick(arr,0,arr.length-1)));
    }

    public static int[] quick(int[] arr,int left,int right){
        int mid = (left+right)/2;
        //这是之后要用的变量
        int l = left;
        int r = right;
        int indexValue = arr[mid];
        int temp = 0;
        //要左右与中值比较并且交换位置
        while (l<r) {
            while (arr[l] < indexValue) {
                l++;
            }
            while (arr[r] > indexValue) {
                r--;
            }
            if (l >= r) {//说明左边已经有序，不需用在进行排序
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            if (arr[l] == indexValue) {
                r--;
            }

            if (arr[r] == indexValue) {
                l++;
            }
        }

        if (l == r){//left = 0; r = 1时或无限递归
            l++;
            r--;
        }
        //进行递归
        if (left < r){
            quick(arr,left,r);
        }

        if (right > l){
            quick(arr,l,right);
        }

        return arr;

    }
}
